package sort;

public class CountingSort {

    public static void countingSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        // 找出数组中的最大值和最小值
        int max = arr[0];
        int min = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
            if (num < min) {
                min = num;
            }
        }

        // 创建计数数组，并初始化为0
        int range = max - min + 1;
        int[] countArr = new int[range];

        // 统计每个数值出现的次数
        for (int num : arr) {
            countArr[num - min]++;
        }

        // 计算位置信息
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] += countArr[i - 1];
        }

        // 创建输出数组
        int[] outputArr = new int[arr.length];

        // 从后向前遍历待排序数组，构建排序后的数组
        for (int i = arr.length - 1; i >= 0; i--) {
            outputArr[countArr[arr[i] - min] - 1] = arr[i];
            countArr[arr[i] - min]--;
        }

        // 将排序后的数组复制回原数组
        System.arraycopy(outputArr, 0, arr, 0, arr.length);
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.print("排序后的数组: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}